package com.wss.lsl.test.driven.arithmetic.search;

/**
 * 二分搜索：常规模式
 * 
 * @author wei.ss
 * @date 2017年3月10日
 * @copyright wonhigh.cn
 */
public class BinArraySearchNormal<T extends Comparable<T>> extends
		BinArraySearchFirst<T> {

	public BinArraySearchNormal(T[] data) {
		super(data);
	}

	@Override
	public int search(T e) {

		int l = 0, u = data.length - 1;
		int m;
		int p = -1;
		while (l <= u) {
			m = (l + u) / 2;
			if (data[m].compareTo(e) < 0) {
				l = m + 1;
			} else if (data[m].compareTo(e) == 0) {
				p = m;
				break;
			} else {
				u = m - 1;
			}
		}

		return p;
	}

	@Override
	public void validate(T e, int p) {
		if (p == -1) {
			int p2 = -1;
			for (int i = 0; i < data.length; i++) {
				if (data[i].equals(e)) {
					p2 = i;
					break;
				}
			}
			if (p2 != p) {
				throw new RuntimeException(String.format(
						"元素在数组中，查找的下标不正确：e=%s,p=%s", e, p));
			}
		} else if (!data[p].equals(e)) {
			throw new RuntimeException(String.format(
					"元素不在数组中，查找的下标不正确：e=%s,p=%s", e, p));
		}
	}
}
